package middle;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数数组nums，你可以对它进行一些操作。
 *
 * 每次操作中，选择任意一个nums[i]，删除它并获得nums[i]的点数。之后，你必须删除 所有 等于nums[i] - 1 和 nums[i] + 1的元素。
 *
 * 开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
 *
 * 示例 1：
 *
 * 输入：nums = [3,4,2]
 * 输出：6
 * 解释：
 * 删除 4 获得 4 个点数，因此 3 也被删除。
 * 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
 *
 * 链接：https://leetcode.cn/problems/delete-and-earn
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class DeleteAndEarn {
    /**
     * 类似198.打家劫舍的解法
     * */
    class Solution {
        public int deleteAndEarn(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>(nums.length);
            int ans = 0;
            int maxVal = 0;
            int dp = 0;
            int ndp= 0;
            // 找到最大值
            for (int n : nums) {
                maxVal = Math.max(n, maxVal);
            }
            // 把所有的数字的和计算出来，并存储到map中
            for (int n : nums) {
                map.put(n, map.getOrDefault(n, 0) + n);
            }
            for (int i = 1; i <= maxVal; i++) {
                int t = dp;
                dp = Math.max(map.getOrDefault(i, 0) + ndp, t);
                ndp = t;
                ans = Math.max(ans, dp);
            }
            return ans;
        }
    }
}
